package exercises.newcoder.solution;

import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=188&&tqId=38602&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC75 数组中只出现一次的两个数字</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * <p>
 * 数据范围：数组长度 ，数组中每个数的大小
 * 要求：空间复杂度 ，时间复杂度
 *
 * <p>
 * 提示：输出时按非降序排列。
 * <p>
 * 示例1
 * <p>
 * 输入：
 * [1,4,1,6]
 * <p>
 * 返回值：
 * [4,6]
 * <p>
 * 说明：
 * 返回的结果中较小的数排在前面
 * <p>
 * 示例2
 * <p>
 * 输入：
 * [1,2,3,3,2,9]
 * <p>
 * 返回值：
 * [1,9]
 *
 * @author or2
 * @date 2021年09月28日 时间: 10:15
 */
public class NC75 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce(int[] array) {
        int bias = 0;
        for (int i = 0, arrayLength = array.length; i < arrayLength; i++)
            bias ^= array[i];
        bias = (~bias + 1) & bias;

        int num1 = 0, num0 = 0;
        for (int i = 0, arrayLength = array.length; i < arrayLength; i++) {
            int num = array[i];
            if ((num & bias) > 0)
                num1 ^= num;
            else
                num0 ^= num;
        }

        if (num1 > num0)
            return new int[]{num0, num1};
        else
            return new int[]{num1, num0};
    }

    public static void Acm(String... arg) {
        Scanner scanner = new Scanner(System.in);
        int amount = scanner.nextInt();
        int[] arr = new int[amount];
        int bias = 0;
        for (int i = 0, len = arr.length; i < len; i++) {
            int num = scanner.nextInt();
            arr[i] = num;
            bias ^= num;
        }
        bias = (~bias + 1) & bias;

        int num1 = 0, num0 = 0;
        for (int i = 0, arrayLength = arr.length; i < arrayLength; i++) {
            int num = arr[i];
            if ((num & bias) > 0)
                num1 ^= num;
            else
                num0 ^= num;
        }

        if (num1 > num0)
            System.out.println(num0 + " " + num1);
        else
            System.out.println(num1 + " " + num0);
    }
}
